"""
难度：中等
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：
   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
"""

"""
深度优先搜索。

先判断特例，如果 A、B 都为空树，则直接返回 False。
然后递归判断 A、B 是否相等。
如果 A、B 相等，则返回 True。
如果 A、B 不相等，则递归判断 B 是否是 A 的左子树的子结构，或者 B 是否是 A 的右子树的子结构，如果有一种满足，则返回 True，如果都不满足，则返回 False。
递归判断 A、B 是否相等的具体方法如下：

如果 B 为空树，则直接返回 False，因为空树不是任意一棵树的子结构。
如果 A 为空树或者 A 节点的值不等于 B 节点的值，则返回 False。
如果 A、B 都不为空，且节点值相同，则递归判断 A 的左子树和 B 的左子树是否相等，判断 A 的右子树和 B 的右子树是否相等。如果都相等，则返回 True，否则返回 False。

"""

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not A or not B:
            return False
        if self.hasSubStructure(A,B):
            return True
        return self.isSubStructure(A.left,B) and self.isSubStructure(A.right,B)

    def hasSubStructure(self,A:TreeNode,B:TreeNode) ->bool:
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.hasSubStructure(A.left,B.left) and self.hasSubStructure(A.right,B.right)
    
